class Node{
  constructor(key, left = null, right = null, h = 0){
    this.left = left;
    this.right = right;
    this.key = key;
    this.h = h;
  }
}

function update_height(root){
  root.h = Math.max(root.left.h, root.right.h) + 1;
}

function left_rotate(root) {
  const newRoot = root.right;

  //把新root节点的左子树挂到 旧root节点的右边
  root.right = newRoot.left;

  // 把旧root节点，挂到新root左边
  newRoot.left = root;
  
  update_height(root);
  update_height(newRoot);
  return newRoot;
}

function right_rotate() {
  const newRoot = root.left;
  root.left = newRoot.right;
  newRoot.right = root;
  update_height(root);
  update_height(newRoot);
  return newRoot;
}

// 调整二叉树为平衡树
Node.prototype.maintain = function (root) {
  if(Math.abs(root.left.h - root.right.h) < 2) return root;
  let val = root.key;
  if(root.left.h > root.right.h) {
    if(root.left.right.h > root.left.left.h) { // LR型
      root.left = left_rotate(root.left); // 小左旋
    }

    // LR , LL 共同的操作
    root = right_rotate(root); // 大右旋 
  } else {
    if(root.right.left.h > root.right.right.h) { // RL 型
      root.right = right_rotate(root.right); // 小右旋
    }

    // RL , RR 共同的操作
    root = root.left_rotate(root); // 大左旋
  }
  return root;
}

Node.prototype.getNode = function(key) {
  return new Node(key);
}
Node.prototype.insert = function (root, key) {
  if(!root) return this.getRootNode(key);
  if(root.key === key) return root;
  if(key < root.key) {
    root.left = this.insert(root.left, key);
  } else if(key > root.key) {
    root.right = this.insert(root.right, key);
  }
  // 更新当前节点高度
  update_height(root);
  return this.maintain(root);
}
Node.prototype.erase = function(root, key){
  if(!root) return root;
  if(key < root.key) {
    this.erase(root.left, key);
  } else if(key > root.key) {
    this.erase(root.right, key);
  } else {
    if(!root.left || !root.right) {
      // 兼容度为0 和度为 1
      const temp = root.left ? root.left : root.right;
      delete root;
      return temp;
    } else {
      const temp = predesccessor(root);
      root.key = temp.key;
      root.left = erase(root.left, temp.key);
    }
  }
  update_height(root);
  return this.maintain(root);
}
